\begin{abstract}

Nested-word automata (NWAs) are a language formalism that helps bridge
the gap between finite-state automata and pushdown automata. NWAs can express
some context-free properties, such as parenthesis matching, yet retain all
the desirable closure characteristics of finite-state automata.

This document describes OpenNWA, a C++ implementation of NWAs.  OpenNWA
provides the expected automata-theoretic operations, such as intersection,
determinization, and complementation, as well as query operations. It is
packaged with WALi---\textit{W}eighted \textit{A}utomata
\textit{Li}brary---and interoperates closely with the weighted pushdown
system portions of WALi.


\end{abstract}


The OpenNWA library is available from
\url{http://www.cs.wisc.edu/wpis/OpenNWA/}. It is packaged with the
\textit{W}eighted \textit{A}utomata \textit{Li}brary, WALi. WALi 4.0 is
paired with the first public release of OpenNWA, which is what this document
describes. Building instructions can be found in \texttt{README.txt} in the
root directory of the OpenNWA/WALi distribution.

We assume the reader is familiar with nested words and
nested-word automata; if not, \appref{nwa-definition} provides the definition
we use and
Alur et al.~\cite{DLT:AM2006,JACM:AM2009} describe them in detail. Our
implementation corresponds to the definition from the DLT 2006
paper~\cite{DLT:AM2006}; relative to follow-up work~\cite{JACM:AM2009}, this definition removes
the distinction between the machine's linear and hierarchical states, and on
a call transition always stacks the source state. In addition, we only require that the
final linear state be accepting for an NWA to accept a
word. (Following~\cite{JACM:AM2009}, this specific variant is a
``weakly-hierarchical, linearly-accepting'' NWA.)

The terminology used in the interface of the package is geared
toward program analysis, so we use terms such as ``call site'' and ``return
site'' to refer to states of the NWA even though they take on different
meanings in different contexts.

In contrast to the standard definitions, we allow internal $\epsilon$
transitions (but not call or return $\epsilon$ transitions). We also allow ``wild''
transitions, which match any single symbol. (Wilds \emph{can} appear on calls
and returns.)

%The NWAs in this library have support for balanced and unbalanced-left nested
%words only, and does not provide support for any words with pending
%returns. (That is, we support balanced words and nested-word prefixes, but
%not nested-word suffixes or general nested words.)
\clearpage
\tableofcontents

\vspace{2\baselineskip}




\clearpage

\section{Library Overview}
\label{Se:Nested Word Automata}

The core of the NWA library is in the namespace \texttt{opennwa}. It
includes the classes \texttt{NestedWord}, \texttt{Nwa}, and others.

There are a large number of non-member functions that operate on NWAs. These
are divided into three sub-namespaces:
\texttt{opennwa::query}, \texttt{opennwa::construct}, and
\texttt{opennwa::nwa\_pds}. There is also an experimental parser in
\texttt{opennwa}.

Finally, there are some operations and classes provided by WALi that OpenNWA
uses. This mostly consists of the key-handling code,
but also includes the WPDS portions of WALi.

Throughout this document, include paths are relative to the \texttt{Source}
directory from the WALi/OpenNWA distribution.

Section \ref{Se:ExampleUse} illustrates a simple sample use of the library.

\subsection{NWA core classes}

These types live in namespace \texttt{opennwa}:

\begin{functionlist}
  \functionitem[\texttt{NestedWord}] Implements a single nested word. Currently the only
    operation that can be performed using one is checking whether a
    \texttt{NestedWord} is a member of an \texttt{Nwa}'s language. Defined in
    \texttt{opennwa/NestedWord.hpp}. See \sectref{class-nested-word}.
  \functionitem[\texttt{Nwa}] Implements a nested-word automaton. Defined in
    \texttt{opennwa/Nwa.hpp} with a forward declaration in \texttt{opennwa/NwaFwd.hpp}.
    See
    \sectref{NWA-class}. (\sectref{serialization} also discusses member
    functions related to serializing an NWA.)
  \functionitem[\texttt{ref\_ptr$<$T$>$}] This is a reference-counted, intrusive
    smart-pointer template. (``Intrusive'' means that the pointed-to type
    must be modified to include a \texttt{count} field used by the
    pointer. This is most conveniently done by subclassing
    \texttt{wali::Countable}.) Defined in
    \texttt{wali/ref\_ptr.hpp}. However, a \texttt{using wali::ref\_ptr}
    declaration brings this type into the \texttt{opennwa} namespace as well;
    we suggest preferring the latter version. In addition, there are typedefs of
    both \texttt{ref\_ptr$<$Nwa$>$} and \texttt{ref\_ptr$<$NestedWord$>$},
    and we suggest preferring those names.
  \functionitem[\texttt{NwaRefPtr}] \texttt{NwaRefPtr} is a typedef of \texttt{ref\_ptr$<$Nwa$>$}.
    Defined in \texttt{opennwa/NwaFwd.hpp}.
  \functionitem[\texttt{State} and \texttt{Symbol}] These are both typedefs of
    \texttt{wali::Key} (see below). Both are defined in
    \texttt{opennwa/NwaFwd.hpp}. \emph{Note:} the use of keys for both
    states and symbols means that they can be confused from a types
    perspective, so use caution that this does not happen. In addition, a
    future version of the library may change \texttt{State} and
    \texttt{Symbol} to be distinct types.
  \functionitem[\texttt{StateSet} and \texttt{SymbolSet}] These are typedefs of
    \texttt{std::set}s of the corresponding type. (Client code should not
    rely on this
    fact; it could change to be an \texttt{unordered\_map} or other similar
    container.) Both are defined in \texttt{opennwa/NwaFwd.hpp}.
  \functionitem[\texttt{ClientInfo}] This class holds client-specific information that
    is associated with a state. Client code can subclass \texttt{ClientInfo} and use
    functions of the \texttt{Nwa} class to attach instances to states. To use,
    include \texttt{opennwa/ClientInfo.hpp}. See \sectref{client-info}.
  \functionitem[\texttt{WeightGen}] This abstract class describes how to assign weights
    to transitions of the NWA, and is used both when converting an NWA to a
    PDS and when doing prestar/poststar queries on the NWA directly. To use,
    include \texttt{opennwa/WeightGen.hpp}. See \sectref{NWAtoPDS}.
\end{functionlist}


\subsection{NWA non-member functions}

The library provides a large number of non-member functions for operating on
NWAs. These are partitioned into the following namespaces:

\begin{functionlist}
  \functionitem[\texttt{opennwa::query}] This namespace provides functions for
    querying an automaton. The functions in this namespace are:
    \begin{itemize}
      \item Functions that query transitions of
        the NWA, returning information about one of the states or the symbol
        in transitions that meet some criteria. (For example, ``give me all
        states that appear as the target state of an internal transition with
        this source state.'') See \sectref{query-transitions}.
      \item Determining whether two NWAs have any states in
        common. See \sectref{query-automaton}.
      \item Determining whether an \texttt{Nwa} is deterministic. See
        \sectref{query-automaton}.
      \item Determining whether a \texttt{NestedWord} is a member of the
        language of an NWA. See \sectref{query-language}.
      \item Determining whether the language of an NWA is empty. See
        \sectref{query-language}.
      \item Determining whether the languages of two NWAs are equal, or if
        one is a subset of the other. See \sectref{query-language}.
      \item Prestar and poststar operations on an NWA. See
        \sectref{query-language}.
    \end{itemize}
    
  \functionitem[\texttt{opennwa::construct}] This namespace provides functions for
    constructing an NWA. Functions in this namespace are standard,
    automata-theoretic operations such as intersection, union, concatenation,
    Kleene star, and reversal. See \sectref{Building NWAs}.
  \functionitem[\texttt{opennwa::nwa\_pds}] This namespace provides functions for
    converting between NWAs and WPDSs, and related functions. (Note that
    construction of an NWA from a WPDS is in this namespace, not in
    \texttt{construct}.) See \sectref{Conversions}.
  \functionitem[\texttt{opennwa}] This namespace, in addition to the items already
    discussed, provides an experimental parser for a serialization format of
    NWAs. See \sectref{serialization}.
\end{functionlist}


\subsection{Supporting features from WALi}

The NWA library uses these portions of the standard WALi library. Unless
otherwise specified, they are in namespace \texttt{wali}. See \cite{wali}.

\begin{functionlist}
  \functionitem[\texttt{Key}] A \texttt{Key} is a unique identifier naming states and symbols in an
    NWA or NestedWord. It is actually a typedef of an integer, though client
    code should not rely on this precise type. Declared in
    \texttt{wali/Key.hpp}.

  \functionDef{Key}{getKey}{...}{} This function produces a key from some input. If
    the input has not been seen before, it returns a new key; if it has, then
    it returns the same key as before. (One can think of this as translating
    whatever unique identifier is known by the client code to the
    \texttt{Key} needed by OpenNWA and WALi.) Overloads of this function are provided for
    the following types:
    \begin{itemize}
      \item \texttt{std::string const \&}
      \item \texttt{char *}
      \item \texttt{int}
      \item \texttt{std::set<Key> const \&}
      \item \texttt{Key, Key} (this is a two-argument version of
        \texttt{getKey})
      \item \texttt{key\_src\_t}
    \end{itemize}
    The final overload, for \texttt{key\_src\_t}, is a \texttt{ref\_ptr} to a
    \texttt{KeySource} object. \texttt{KeySource} is an abstract class that
    client code can subclass to provide a translation to \texttt{Key}s for
    arbitrary types.

    All overloads are declared in \texttt{wali/Key.hpp}.

  \functionDef{std::string}{key2str}{Key k}{}
    \texttt{key2str} is an ``inverse'' of \texttt{getKey}, except that it
    always returns a string representation. If the key was created with
    \texttt{getKey(std::string const \&)} in the first place, this
    returns a copy of the original string.\footnote{For \texttt{int}s, it is the
    textual representation of the original number. For a \texttt{set<Key>},
    it is the set printed in standard set notation. For a pair of keys, it is
    the pair printed as an ordered pair. In general, it is the result of
    calling \texttt{key\_src\_t::print}. See the \texttt{print} function in
    each of the files \texttt{wali/*Source.cpp}.} Declared in
    \texttt{wali/Key.hpp}.

  \functionitem[\texttt{wali::wfa::WFA}] This is a weighted finite automaton. It is
    used in NWA poststar and prestar queries in much the same manner as in
    WPDS poststar and prestar queries. Defined in \texttt{wali/wfa/WFA.hpp}.

  \functionitem[\texttt{wali::wpds::WPDS}] This is a weighted pushdown system. NWAs use
    WPDSs behind the scenes when doing poststar and prestar queries, and the
    library provides conversion routines between the two automata
    types. Defined in \texttt{wali/wpds/WPDS.hpp}.
\end{functionlist}


\subsection{Simple example use of the library}
\label{Se:ExampleUse}
The following is an illustration of basic operations of the library. The full
code is available in the file \texttt{Doc/NWA\_tex/Example/example.cpp} in the
OpenNWA distribution.

\inputminted{c++}{Example/example-abbrev.cpp}

